package com.wzh.test.dynamicprograming;

import java.util.Arrays;

/**
 * 有一个数据[1,3,5,6,7,8,9]
 * 现在想从中找出n个数字，要求它们相加之和是最大的
 * 另外，要求相邻的两个数字不能同时出现
 * opt(9) = max(9+opt(prev(9)),opt(8))
 */
public class Demo1 {
    public static int[] arr = {4,1,1,9,1};

    public static void main(String[] args) {
        int result = recOpt(4);
        System.out.println(result);

        int result2 = dpOpt();
        System.out.println(result2);


    }

    public static int recOpt(int i){
        if(i == 0){
            return arr[0];
        }else if(i == 1){
            return Math.max(arr[0],arr[1]);
        }
        return Math.max(arr[i] + recOpt(i - 2), recOpt(i- 1));
    }

    public static int dpOpt(){
        int[] opt = Arrays.copyOf(arr,arr.length);
        opt[0] = arr[0];
        opt[1] = Math.max(arr[0],arr[1]);
        for(int i = 2; i < arr.length;i++){
            opt[i] = Math.max(arr[i] + opt[i - 2],opt[i - 1]);
        }
        return opt[arr.length - 1];
    }
}
